package com.hy.treeNode2;

import com.hy.treeNode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class TreeNodeCountNodes {


    /**
     * 222.完全二叉树的节点个数
     * 力扣题目链接
     *
     * 给出一个完全二叉树，求出该树的节点个数。
     *
     * 示例 1：
     *
     * 输入：root = [1,2,3,4,5,6]
     * 输出：6
     *
     *
     * @param root
     * @return
     */

    // 层序遍历
    public int countNodes(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null){
            return 0;
        }
        deque.offerLast(root);

        int count = 0;
        while (!deque.isEmpty()){
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                count++;
                TreeNode node = deque.pollFirst();
                if (node.left != null){
                    deque.offerLast(node.left);
                }
                if(node.right != null){
                    deque.offerLast(node.right);
                }

            }
        }
        return count;
    }

    // 递归
    public int countNodes2(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftCount = countNodes2(root.left);
        int rightCount = countNodes2(root.right);
        return (leftCount + rightCount) + 1;
    }

    public static void main(String[] args) {
        TreeNode leftNode3 = new TreeNode(8, null, null);
        TreeNode rightNode3 = new TreeNode(8, null, null);

        TreeNode leftNode2 = new TreeNode(4, null, null);
        TreeNode rightNode2 = new TreeNode(3, null, rightNode3);

        TreeNode leftNode1 = new TreeNode(3, leftNode3, null);
        TreeNode rightNode1 = new TreeNode(4, null, null);

        TreeNode leftNode = new TreeNode(2, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(2, leftNode2, rightNode2);

        TreeNode root = new TreeNode(1, leftNode, rightNode);
        TreeNodeCountNodes treeNodeCountNodes = new TreeNodeCountNodes();
        System.out.println("完全二叉树的节点数(迭代)："+treeNodeCountNodes.countNodes(root));
        System.out.println("完全二叉树的节点数(递归)："+treeNodeCountNodes.countNodes2(root));
    }
}
